경사하강법을 이용한 최적화

이제 우리는 실수값 함수(real-valued function)의 최솟값을 푸는 문제를 고려한다.

여기서 $f : \mathbb{R}^d \rightarrow \mathbb{R}$ 은 당면한 기계 학습 문제를 포착하는 목적 함수(objective function)이다. 우리는 함수 $f$ 가 미분 가능하며, 닫힌 형태(closed form)의 해석적인 해를 찾을 수 없다고 가정한다.

$\quad$ 경사 하강법은 1차 최적화 알고리즘(first-order optimization algorithm)이다. 경사 하강법을 사용하여 함수의 국소 최솟값을 찾기 위해, 현재 지점에서의 함수 기울기의 음수(negative of the gradient)에 비례하는 스텝을 밟는다. [5.1절]에서 기울기는 가장 가파른 상승(steepest ascent) 방향을 가리킨다는 것을 상기하라. 또 다른 유용한 직관은 함수가 특정 값을 가지는 선들의 집합( $f(\boldsymbol{x}) = c$ , 여기서 $c \in \mathbb{R}$ )을 고려하는 것인데, 이는 등고선(contour lines)으로 알려져 있다. 기울기는 우리가 최적화하고자 하는 함수의 등고선과 직교(orthogonal)하는 방향을 가리킨다.

$\quad$ 다변량 함수를 고려해 보자. 특정 위치 $\boldsymbol{x}_0$ 에서 시작하는 공이 있는 표면(함수 $f(\boldsymbol{x})$ 로 묘사됨)을 상상해 보라. 공을 놓으면, 공은 가장 가파른 하강 방향으로 내리막을 따라 이동할 것이다. 경사 하강법은 어떤 사람이 $\boldsymbol{x}_0$ 에서 $f$ 의 음의 기울기 $-((\nabla f)(\boldsymbol{x}_0))^\top$ 방향으로 이동할 때 $f(\boldsymbol{x}_0)$ 가 가장 빠르게 감소한다는 사실을 이용한다. 이 책에서 우리는 함수들이 미분 가능하다고 가정하며, 독자들에게 7.4절의 더 일반적인 설정을 참고하도록 한다. 그러면 만약

작은 스텝 사이즈(step-size) $\gamma \geqslant 0$ 에 대해, $f(\boldsymbol{x}_1) \leqslant f(\boldsymbol{x}_0)$ 이 성립한다. 차원이 맞지 않기 때문에 기울기에 전치(transpose)를 사용한다는 점에 유의하라. (우리는 기울기에 대해 행 벡터(row vectors) 관례를 사용한다.)

$\quad$ 이러한 관찰은 우리가 단순한 경사 하강법 알고리즘을 정의할 수 있게 해준다: 만약 우리가 함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}, \boldsymbol{x} \mapsto f(\boldsymbol{x})$ 의 국소 최적값 $f(\boldsymbol{x}_*)$ 를 찾고자 한다면, 우리는 최적화하고자 하는 파라미터의 초기 추정값 $\boldsymbol{x}_0$ 로 시작하여 다음 식에 따라 반복(iterate)한다.

적절한 스텝 사이즈 $\gamma_i$ 에 대해, 수열 $f(\boldsymbol{x}_0) \geqslant f(\boldsymbol{x}_1) \geqslant \dots$ 는 국소 최솟값으로 수렴(converges)한다.

주의 (Remark). 경사 하강법은 최솟값 근처에서 상대적으로 느려질 수 있다: 그것의 점근적 수렴 속도(asymptotic rate of convergence)는 다른 많은 방법들보다 열등하다. 언덕을 굴러 내려가는 공의 비유를 사용하자면, 표면이 길고 좁은 계곡(long, thin valley)일 때, 이 문제는 불량 조건(poorly conditioned, Trefethen and Bau III, 1997)이 된다. 불량 조건의 볼록 문제에서, 그래디언트가 최솟값으로 가는 가장 짧은 방향에 거의 직교(orthogonal)하는 방향을 가리키기 때문에 경사 하강법은 점차 “지그재그(zigzags)” 행보를 보이게 된다; 그림 7.3을 참조하라.

7.1.1 Step-size

스텝 사이즈

앞서 언급했듯이, 경사 하강법에서 좋은 스텝 사이즈를 선택하는 것은 중요하다. 스텝 사이즈가 너무 작으면 경사 하강법은 느려질 수 있다. 스텝 사이즈를 너무 크게 선택하면, 경사 하강법은 목표를 지나치거나(overshoot), 수렴에 실패하거나, 심지어 발산(diverge)할 수 있다. (스텝 사이즈는 학습률(learning rate)이라고도 불린다.) 우리는 다음 절에서 모멘텀(momentum)의 사용에 대해 논의할 것이다. 이는 경사 업데이트의 불규칙한 동작을 부드럽게 하고 진동(oscillations)을 감쇠시키는 방법이다.

$\quad$ 적응형 경사 방법(Adaptive gradient methods)은 함수의 국소적 특성에 따라 매 반복마다 스텝 사이즈를 재조정(rescale)한다. 두 가지 간단한 휴리스틱이 있다 (Toussaint, 2012):

• 경사 스텝 이후 함수값이 증가하면 스텝 사이즈가 너무 컸던 것이다. 스텝을 취소(undo)하고 스텝 사이즈를 줄여라.
• 함수값이 감소하면 스텝이 더 클 수도 있었다. 스텝 사이즈를 늘려보라.
  비록 “취소(undo)” 스텝이 자원의 낭비처럼 보일 수 있지만, 이 휴리스틱을 사용하면 단조 수렴(monotonic convergence)을 보장한다.

주의 (Remark). $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}$ 라는 선형 방정식 시스템의 해에 적용될 때, 경사 하강법은 느리게 수렴할 수 있다. 경사 하강법의 수렴 속도는 행렬 $\boldsymbol{A}$ 의 최대 특잇값과 최소 특잇값의 비율인 조건수(condition number) $\kappa = \frac{\sigma(\boldsymbol{A})_{\max}}{\sigma(\boldsymbol{A})_{\min}}$ 에 의존한다 ([4.5절]). 조건수는 본질적으로 가장 많이 구부러진 방향 대 가장 적게 구부러진 방향의 비율을 측정하며, 이는 불량 조건 문제가 길고 좁은 계곡이라는 우리의 심상과 일치한다: 그것들은 한 방향으로는 매우 구부러져 있지만, 다른 방향으로는 매우 평평하다. $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}$ 를 직접 푸는 대신, $\boldsymbol{P}^{-1}(\boldsymbol{A}\boldsymbol{x} - \boldsymbol{b}) = \boldsymbol{0}$ 을 풀 수도 있다. 여기서 $\boldsymbol{P}$ 는 사전 조건자(preconditioner)라고 불린다. 목표는 $\boldsymbol{P}^{-1}\boldsymbol{A}$ 가 더 나은 조건수를 가지면서 동시에 $\boldsymbol{P}^{-1}$ 을 계산하기 쉽도록 $\boldsymbol{P}^{-1}$ 을 설계하는 것이다.

7.1.2 Gradient Descent With Momentum

모멘텀을 동반한 경사 하강법

그림 7.3에 예시된 바와 같이, 최적화 표면의 곡률이 불량하게 스케일된(poorly scaled) 영역이 존재한다면 경사 하강법의 수렴은 매우 느려질 수 있다. 이 곡률 때문에 경사 하강법 스텝은 계곡의 벽 사이를 널뛰기(hops)하며, 작은 스텝으로 최적값에 접근하게 된다. 수렴을 개선하기 위해 제안된 조작(tweak)은 경사 하강법에 약간의 기억(memory)을 부여하는 것이다. (Goh (2017)는 모멘텀을 동반한 경사 하강법에 대한 직관적인 블로그 포스트를 작성했다.)

$\quad$ 모멘텀을 동반한 경사 하강법(Rumelhart et al., 1986)은 이전 반복(iteration)에서 일어났던 일을 기억하기 위해 추가적인 항(term)을 도입하는 방법이다. 이 기억은 진동(oscillations)을 감쇠시키고 그래디언트 업데이트를 부드럽게 만든다. 공의 비유를 이어가자면, 모멘텀 항은 방향을 바꾸기를 꺼리는 무거운 공의 현상을 모방한다. 핵심 아이디어는 이동 평균(moving average)을 구현하기 위해 기억을 가진 그래디언트 업데이트를 수행하는 것이다. 모멘텀 기반 방법은 매 반복 $i$ 마다의 업데이트 $\Delta \boldsymbol{x}_i$ 를 기억하고, 현재와 이전 그래디언트들의 선형 결합(linear combination)으로 다음 업데이트를 결정한다.

여기서 $\alpha \in [0, 1]$ 이다. 때때로 우리는 그래디언트를 단지 근사적으로만 알게 될 것이다. 그러한 경우, 모멘텀 항은 그래디언트의 각기 다른 노이즈가 섞인 추정치들을 평균 내어 상쇄시키기 때문에 유용하다. 근사적인 그래디언트를 얻는 특히 유용한 한 가지 방법은 확률적 근사(stochastic approximation)를 사용하는 것이며, 이에 대해서는 다음에 논의한다.

7.1.3 Stochastic Gradient Descent

확률적 경사 하강법

그래디언트를 계산하는 것은 시간이 매우 많이 소요될 수 있다. 하지만, 종종 그래디언트의 “값싼(cheap)” 근사치를 찾는 것이 가능하다. 근사된 그래디언트가 진짜 그래디언트와 대략적으로 같은 방향을 가리키는 한, 그것을 근사하는 것은 여전히 유용하다.

$\quad$ 확률적 경사 하강법(종종 SGD로 줄여 씀)은 미분 가능한 함수들의 합으로 쓰인 목적 함수를 최소화하기 위한 경사 하강법의 확률적 근사(stochastic approximation)이다. 여기서 ‘확률적(stochastic)’이라는 단어는 우리가 그래디언트를 정확하게 알지 못하며, 대신 노이즈가 섞인 근사치만을 안다는 사실을 인정한다는 것을 의미한다. 근사된 그래디언트들의 확률 분포를 제약(constraining)함으로써, 우리는 SGD가 수렴할 것이라는 점을 이론적으로 여전히 보장할 수 있다.

$\quad$ 기계 학습에서, $n = 1, \dots, N$ 개의 데이터 포인트가 주어졌을 때 우리는 종종 각 예제 $n$ 에 의해 발생한 손실(losses) $L_n$ 들의 합인 목적 함수를 고려한다. 수학적 표기법으로 우리는 다음과 같은 형태를 갖는다.

여기서 $\boldsymbol{\theta}$ 는 관심 있는 파라미터들의 벡터이다. 즉, 우리는 $L$ 을 최소화하는 $\boldsymbol{\theta}$ 를 찾고자 한다. 회귀(Regression, 9장)에서의 한 예는 음의 로그 가능도(negative log-likelihood)이며, 이는 개별 예제들의 로그 가능도에 대한 합으로 표현되어 다음과 같이 된다.

여기서 $\boldsymbol{x}_n \in \mathbb{R}^D$ 는 훈련 입력(training inputs), $y_n$ 은 훈련 타깃(training targets), 그리고 $\boldsymbol{\theta}$ 는 회귀 모델의 파라미터이다.

$\quad$ 이전에 소개된 표준 경사 하강법은 “배치(batch)” 최적화 방법이다. 즉, 최적화는 다음과 같이 파라미터 벡터를 업데이트함으로써 전체 훈련 세트를 사용하여 수행된다.

적절한 스텝 사이즈 파라미터 $\gamma_i$ 에 대해 말이다. 이 합(sum) 그래디언트를 평가하는 것은 모든 개별 함수 $L_n$ 들로부터 그래디언트를 평가해야 하므로 비용이 많이 들 수 있다. 훈련 세트가 엄청나게 크고/크거나 간단한 공식이 존재하지 않을 때, 그래디언트들의 합을 평가하는 것은 매우 비싸진다.

$\quad$ 식 (7.15)의 항 $\sum_{n=1}^N (\nabla L_n(\boldsymbol{\theta}_i))$ 를 고려해 보자. 우리는 $L_n$ 의 더 작은 집합(smaller set)에 대해 합을 취함으로써 연산량을 줄일 수 있다. $n = 1, \dots, N$ 에 대해 모든 $L_n$ 을 사용하는 배치 경사 하강법과 대조적으로, 우리는 미니 배치 경사 하강법(mini-batch gradient descent)을 위해 $L_n$ 의 부분 집합(subset)을 무작위로 선택한다. 극단적인 경우, 우리는 그래디언트를 추정하기 위해 무작위로 오직 단 하나의 $L_n$ 만을 선택할 수도 있다. 데이터의 부분 집합을 취하는 것이 왜 합리적인지에 대한 핵심 통찰은, 경사 하강법이 수렴하기 위해서는 오직 그래디언트가 진짜 그래디언트의 ‘불편 추정량(unbiased estimate)’이기만 하면 된다는 것을 깨닫는 데 있다. 사실 식 (7.15)의 $\sum_{n=1}^N (\nabla L_n(\boldsymbol{\theta}_i))$ 항은 그래디언트의 기댓값(Expected Value, 6.4.1절)에 대한 경험적 추정치(empirical estimate)이다. 따라서 기댓값에 대한 그 어떤 다른 불편 경험적 추정치(예를 들어 데이터의 임의의 서브샘플을 사용하는 것)라도 경사 하강법의 수렴을 위해 충분할 것이다.
주의 (Remark). 학습률이 적절한 속도로 감소하고, 비교적 온건한 가정(mild assumptions)들을 만족할 때, 확률적 경사 하강법은 거의 확실하게(almost surely) 국소 최솟값으로 수렴한다 (Bottou, 1998).

$\quad$ 왜 우리는 근사된(approximate) 그래디언트를 사용하는 것을 고려해야 하는가? 한 가지 주요한 이유는 중앙 처리 장치(CPU)나 그래픽 처리 장치(GPU)의 메모리 크기, 또는 연산 시간에 대한 한계와 같은 실용적인 구현상의 제약(constraints) 때문이다. 우리는 그래디언트를 추정하는 데 사용되는 부분 집합(subset)의 크기를, 경험적 평균(empirical means, 6.4.1절)을 추정할 때 표본(sample)의 크기를 생각했던 것과 동일한 방식으로 생각할 수 있다. 큰 미니 배치 크기는 그래디언트에 대한 정확한 추정치를 제공하여, 파라미터 업데이트 시 발생하는 분산(variance)을 줄여준다. 게다가, 큰 미니 배치는 비용(cost)과 그래디언트의 벡터화된(vectorized) 구현에서 고도로 최적화된 행렬 연산의 이점을 활용한다. 분산의 감소는 더 안정적인 수렴으로 이끌지만, 각각의 그래디언트 계산은 더 비싸질 것이다.

$\quad$ 대조적으로, 작은 미니 배치는 추정하기가 빠르다. 만약 우리가 미니 배치의 크기를 작게 유지한다면, 우리의 그래디언트 추정치에 섞여 있는 노이즈(noise)는 우리가 갇힐 수도 있었던 몇몇 나쁜 국소 최적값(bad local optima)으로부터 빠져나오게(get out of) 해줄 것이다. 기계 학습에서, 훈련 데이터에 대한 목적 함수를 최소화함으로써 훈련을 수행하기 위해 최적화 방법들이 사용되지만, 전반적인 목표는 일반화 성능(generalization performance, 8장)을 향상시키는 것이다. 기계 학습의 목표가 반드시 목적 함수의 최솟값에 대한 정밀한(precise) 추정을 필요로 하지는 않기 때문에, 미니 배치 접근법을 사용한 근사적인 그래디언트가 널리 사용되어 왔다. 확률적 경사 하강법은 수백만 장의 이미지에 대해 깊은 신경망을 훈련하거나(Dean et al., 2012), 토픽 모델(Hoffman et al., 2013), 강화 학습(Mnih et al., 2015), 대규모 가우시안 프로세스 모델의 훈련(Hensman et al., 2013; Gal et al., 2014)과 같은 대규모 기계 학습 문제에서 매우 효과적이다.